from typing import List


class Solution:

    """
    方法：动态规划，dp[i]表示以nums[i]结尾的最长递增子序列长度
    
    Args:
        nums: 输入数组
        
    Returns:
        最长递增子序列的长度
        
    Time: O(n^2) - 两层循环遍历数组
    
    Space: O(n) - dp数组空间
    """
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
          return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
     
    """
     方法： 使用贪心+二分查找求解最长递增子序列问题
            维护一个tails数组，tails[i]表示长度为i+1的递增子序列的最小结尾值
            对于每个数字，二分查找它在tails中的插入位置
            如果插入位置等于当前最大长度，则最大长度加1
     
     Args:
         nums: List[int] - 输入的整数数组
     
     Returns:
         int: 最长递增子序列的长度
     
     Time: O(nlogn) - 遍历数组O(n)，每次二分查找O(logn)
     
     Space: O(n) - 需要一个长度为n的数组存储tails
     """
    def lengthOfLIS1(self, nums: List[int]) -> int:
        tails, res = [0] * len(nums), 0
        for num in nums:
            i, j = 0, res
            while i < j:
                m = (i + j) // 2
                if tails[m] < num:
                    i = m + 1
                else:
                    j = m
            tails[i] = num
            if j == res: res += 1
        return res
        
